#define _CRT_SECURE_NO_WARNINGS 1

#include"Heap.h"

void Swap(HPDateType* e1, HPDateType* e2)
{
	HPDateType tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}
void AdjustUp(HPDateType* date, int child)
{
	assert(date);

	int father = (child - 1) / 2;
	while (child > 0)
	{
		if (date[child] > date[father])
		{
			Swap(date + child, date + father);
			child = father;
			father = (child - 1) / 2;
		}
		else
			break;
	}
}
void AdjustDown(HPDateType* date, int father, int n)
{
	assert(date);
	
	int child = 2 * father + 1;
	while (child < n)
	{
		if (child + 1 < n && date[child + 1] > date[child])
		{
			child += 1;
		}
		if (date[child] > date[father])
		{
			Swap(&date[child], &date[father]);
			father = child;
			child = 2 * father + 1;
		}
		else
			break;
	}
}
void HeapInit(Heap* heap)
{
	assert(heap);

	heap->date = NULL;
	heap->size = heap->capacity = 0;
}
void HeapDestroy(Heap* heap)
{
	assert(heap);
	if(heap->date)
		free(heap->date);
	heap->date = NULL;
	heap->size = heap->capacity = 0;
}

void HeapPush(Heap* heap, HPDateType val)
{
	assert(heap);

	if (heap->size == heap->capacity)
	{
		size_t NewCapacity = heap->capacity == 0 ? 4 : 2 * heap->capacity;
		HPDateType* tmp = (HPDateType*)realloc(heap->date, sizeof(HPDateType) * NewCapacity);
		if (tmp)
		{
			heap->date = tmp;
			heap->capacity = NewCapacity;
		}
	}

	heap->date[heap->size++] = val;
	AdjustUp(heap->date, heap->size - 1);
}
void HeapPop(Heap* heap)
{
	assert(heap);
	assert(heap->size);

	Swap(heap->date, heap->date + heap->size - 1);
	heap->size--;

	AdjustDown(heap->date, 0, heap->size);
}
HPDateType HeapTop(Heap* heap)
{
	assert(heap);
	assert(heap->size);

	return heap->date[0];
}
bool HeapEmpty(Heap* heap)
{
	assert(heap);

	return heap->size == 0 ? true : false;
}
int HeapSize(Heap* heap)
{
	assert(heap);

	return heap->size;
}

